Abstract:

In view of that virtual environment, where there are massive moving objects, a parallel collision detection algorithm based on octree space division and pipeline is presented. The virtual environment is divided into a series of subspaces by octree division. Then it carries on the collision detection between the nodes in the same subspace. The bounding volumes trees are established for every object in the same subspace. The task trees are established by traversing the bounding trees. The tasks are assigned different processors to deal with. Pipelining and multithreads are adopted, parallel collision detection is realized. Experiment results show that comparing with conventional collision detection based on octree, the efficiency of the algorithm is greatly improved.

Key words: octree, collision detection, pipelining, multithreading, OBB(Oriented Bounding Box)